package leetcode.code0827;

/**
 * 827. 最大人工岛 - Java 提交中击败了 35.96% - 感染 #
 *
 * @author CaoYu
 * @date 2021年11月7日
 * @description
 */
public class Solution1 extends Solution827 {

	private int n;
	private int[] islandSize;// 几号岛屿多大
	private int islandNo; // 岛编号
	private int ans;// 最大岛屿
	private boolean[][] check;
	private Integer[][] zero;// 水域 ， 0的位置
	private int pzero;

	@Override
	public int largestIsland(int[][] grid) {
		this.n = grid.length;
		this.check = new boolean[n][n];
		this.islandNo = 2;// 从2开始编号
		this.islandSize = new int[n * n + 2];// 避开01
		this.zero = new Integer[n * n][2];
		this.pzero = 0;
		this.f(grid);// 给岛编号，同时收录水域，记录访问过的位置
		if (this.pzero == 0)// 没有水域
			return n * n;
		if (this.pzero == n * n) {// 没有陆地
			return 1;// 就人工这一块
		}
		this.g(grid);// 遍历水域zero， 看看有没有联通的岛屿， 如果有更新ans
		return ans + 1;
	}

	private void g(int[][] grid) {
		while (this.pzero > 0) {
			Integer[] z = this.zero[--this.pzero];// 水域坐标
			int size = 0;
			int no1 = this.h(grid, z[0] + 1, z[1]);// 联通的岛号
			size = this.islandSize[no1];
			int no2 = this.h(grid, z[0] - 1, z[1]);// 联通的岛号
			if (no2 != no1) {// 不同岛
				size += this.islandSize[no2];
			}
			int no3 = this.h(grid, z[0], z[1] + 1);// 联通的岛号
			if (no3 != no2 && no3 != no1) {// 不同岛
				size += this.islandSize[no3];
			}
			int no4 = this.h(grid, z[0], z[1] - 1);// 联通的岛号
			if (no4 != no3 && no4 != no2 && no4 != no1) {// 不同岛
				size += this.islandSize[no4];
			}
			ans = Math.max(ans, size);
		}

	}

	private int h(int[][] grid, Integer i, Integer j) {// i,j的岛号
		if (i < 0 || i >= n || j < 0 || j >= n) {
			return 0;
		}
		return grid[i][j];
	}

	private void f(int[][] grid) {// 给所有陆地编号
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!check[i][j]) {
					if (grid[i][j] == 0) {// 水域
						this.addZero(i, j);
					} else if (grid[i][j] == 1) {// 未曾抵达的陆地
						this.islandSize[this.islandNo] = this.infect(grid, i, j, this.islandNo);
						this.islandNo++;
					}
				}
			}
		}

	}

	private void addZero(int i, int j) {// 添加一个水域
		this.check[i][j] = true;
		this.zero[this.pzero][0] = i;
		this.zero[this.pzero][1] = j;
		this.pzero++;
	}

	private int infect(int[][] grid, int i, int j, int no) {// 给陆地[i,j]编号为no
		if (check[i][j]) {
			return 0;
		}
		if (grid[i][j] == 0) {
			this.addZero(i, j);
			return 0;
		}
		this.check[i][j] = true;
		int ans = 1;
		grid[i][j] = no;
		if (i + 1 < n && !this.check[i + 1][j])
			ans += this.infect(grid, i + 1, j, no);
		if (i - 1 >= 0 && !this.check[i - 1][j])
			ans += this.infect(grid, i - 1, j, no);
		if (j + 1 < n && !this.check[i][j + 1])
			ans += this.infect(grid, i, j + 1, no);
		if (j - 1 >= 0 && !this.check[i][j - 1])
			ans += this.infect(grid, i, j - 1, no);
		return ans;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug5();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
